<html>
<head><meta charset="utf-8"><title>Formalizing name resolution · t-compiler/rust-analyzer · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/index.html">t-compiler/rust-analyzer</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html">Formalizing name resolution</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="219065811"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219065811" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219065811">(Dec 07 2020 at 10:59)</a>:</h4>
<p>This is a topic to discuss what mathematical models exists for name resolution. Some links:</p>
<ul>
<li><a href="https://web.cecs.pdx.edu/~apt/esop15.pdf">https://web.cecs.pdx.edu/~apt/esop15.pdf</a></li>
<li><a href="https://github.com/brendanzab/moniker">https://github.com/brendanzab/moniker</a></li>
</ul>
<p>cc <span class="user-mention" data-user-id="201857">@Brendan Zabarauskas</span></p>
<p>Overall mood: <a href="https://twitter.com/graydon_pub/status/1052359170601566210">https://twitter.com/graydon_pub/status/1052359170601566210</a></p>
<div class="inline-preview-twitter"><div class="twitter-tweet"><a href="https://twitter.com/graydon_pub/status/1052359170601566210"><img class="twitter-avatar" src="https://pbs.twimg.com/profile_images/1202995163/graycode_normal.png"></a><p>One of these days I want to give a compiler talk called "name lookup is the absolute worst" that's just 100 slides of screaming goat memes.</p><span>- Graydon Hoare (@graydon_pub)</span></div></div>



<a name="219066741"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219066741" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Brendan Zabarauskas <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219066741">(Dec 07 2020 at 11:06)</a>:</h4>
<p>Fwiw I've moved away from using Moniker on Pikelet - I now use a 'trick' called semantic type checking that combines de Bruijn levels and de Bruijn indices for fast evaluation… Locally Nameless just wasn't pulling it's weight for an actual implementation of dependent type theory. Like a lot of things it depends on the context, and what you are trying to do. Name binding is a frightening rabbit warren of a topic.</p>



<a name="219067007"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219067007" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Brendan Zabarauskas <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219067007">(Dec 07 2020 at 11:09)</a>:</h4>
<p>The scope graph stuff is suuper interesting though - I haven't looked to deeply into it though, simply because it wasn't super useful for what I want, which is fast evaluators for dependent type checkers. I'll see if I can remember any more interesting things I've seen.</p>



<a name="219067186"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219067186" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Brendan Zabarauskas <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219067186">(Dec 07 2020 at 11:11)</a>:</h4>
<p>There's was interesting work on contextual modal type theory (most seen in the <a href="http://complogic.cs.mcgill.ca/beluga/">Beluga theorem prover</a>).</p>



<a name="219067359"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219067359" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Brendan Zabarauskas <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219067359">(Dec 07 2020 at 11:12)</a>:</h4>
<p>I had some links in this issue on Pikelet: <a href="https://github.com/pikelet-lang/pikelet/issues/181/">Move away from using Moniker for variable binding</a> - but this was more in relation to dependent type checking.</p>



<a name="219067427"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219067427" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Brendan Zabarauskas <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219067427">(Dec 07 2020 at 11:13)</a>:</h4>
<p><a href="https://www.jstage.jst.go.jp/article/transinf/E101.D/4/E101.D_2017EDP7257/_article">"Name Binding is Easy with Hypergraphs"</a> might be interesting.</p>



<a name="219067543"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219067543" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219067543">(Dec 07 2020 at 11:14)</a>:</h4>
<p>I have a super high-level question:</p>
<p>One of the most interesting bits of Rust's name res is the "fixed point iteration" thing. Ie, things like</p>
<div class="codehilite" data-code-language="Rust"><pre><span></span><code><span class="k">mod</span> <span class="nn">a</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">  </span><span class="k">use</span><span class="w"> </span><span class="n">b</span>::<span class="n">x</span><span class="w"> </span><span class="k">as</span><span class="w"> </span><span class="n">y</span><span class="p">;</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>
<span class="k">mod</span> <span class="nn">b</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w">   </span><span class="k">use</span><span class="w"> </span><span class="n">a</span>::<span class="n">y</span><span class="w"> </span><span class="k">as</span><span class="w"> </span><span class="n">z</span><span class="p">;</span><span class="w"></span>
<span class="w">    </span><span class="k">struct</span> <span class="nc">x</span><span class="p">;</span><span class="w"></span>
<span class="p">}</span><span class="w"></span>
</code></pre></div>
<p>Are there models which handle that? Or are there models only for stack of scopes?</p>



<a name="219067633"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219067633" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Brendan Zabarauskas <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219067633">(Dec 07 2020 at 11:15)</a>:</h4>
<p>Oooooh yeah that looks closer to the Spoofax scope graph stuff</p>



<a name="219067778"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219067778" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Brendan Zabarauskas <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219067778">(Dec 07 2020 at 11:17)</a>:</h4>
<p>Like, I'm not sure if it can handle it - there's been continued work since that paper you linked, but it might be worth trying it out, or even extending it to support it? Like, if it's a student project you could even use the spoofax workbench to make up a prototype?</p>



<a name="219067844"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219067844" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Brendan Zabarauskas <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219067844">(Dec 07 2020 at 11:18)</a>:</h4>
<p><a href="http://www.metaborg.org/en/latest/">http://www.metaborg.org/en/latest/</a></p>



<a name="219068141"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219068141" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219068141">(Dec 07 2020 at 11:21)</a>:</h4>
<p>Yeah, that'd be fun!</p>



<a name="219068182"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219068182" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Brendan Zabarauskas <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219068182">(Dec 07 2020 at 11:21)</a>:</h4>
<p>I think the relevant part of it is <a href="http://www.metaborg.org/en/latest/source/langdev/meta/lang/nabl2/index.html">Static Semantics Definition with NaBL2</a>? Could be wrong though, I only have a vague understanding that the theory of name resolution/scope graph stuff is used in there.</p>



<a name="219068188"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219068188" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219068188">(Dec 07 2020 at 11:21)</a>:</h4>
<p>Although the end goal is to arrive at the production impl of the name resolution, as the current three versions (rustc, rust-analyzer, intellij) are all a bit of a mess</p>



<a name="219068247"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219068247" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219068247">(Dec 07 2020 at 11:22)</a>:</h4>
<p>Heh, the docs do not inspire confidence: <a href="http://www.metaborg.org/en/latest/source/langdev/meta/lang/nabl2/introduction.html#name-resolution-with-scope-graphs">http://www.metaborg.org/en/latest/source/langdev/meta/lang/nabl2/introduction.html#name-resolution-with-scope-graphs</a></p>



<a name="219068272"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219068272" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Brendan Zabarauskas <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219068272">(Dec 07 2020 at 11:22)</a>:</h4>
<p>HAHA oh dear</p>



<a name="219068304"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219068304" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Brendan Zabarauskas <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219068304">(Dec 07 2020 at 11:22)</a>:</h4>
<p>yeah you would probably have to look at the examples or something sadly</p>



<a name="219068366"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219068366" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Brendan Zabarauskas <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219068366">(Dec 07 2020 at 11:23)</a>:</h4>
<p>researchware is always fun</p>



<a name="219068452"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219068452" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219068452">(Dec 07 2020 at 11:24)</a>:</h4>
<p>Production-ready compilers are no less fun, sadly :D</p>



<a name="219068485"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219068485" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Brendan Zabarauskas <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219068485">(Dec 07 2020 at 11:24)</a>:</h4>
<p>I think this might be the implementation? <a href="https://github.com/metaborg/nabl">https://github.com/metaborg/nabl</a></p>



<a name="219068612"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219068612" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Brendan Zabarauskas <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219068612">(Dec 07 2020 at 11:26)</a>:</h4>
<p>They have a funny eclipse IDE thing that you can define languages in using these DSLs</p>



<a name="219068658"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219068658" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Brendan Zabarauskas <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219068658">(Dec 07 2020 at 11:26)</a>:</h4>
<p>I think I've seen demos in videos of Elco Visser playing around</p>



<a name="219068682"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219068682" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219068682">(Dec 07 2020 at 11:27)</a>:</h4>
<blockquote>
<p>HAHA oh dear</p>
</blockquote>
<p>Added appropriate tweet to the first message in the thread</p>



<a name="219068713"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219068713" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Brendan Zabarauskas <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219068713">(Dec 07 2020 at 11:27)</a>:</h4>
<p>amazing!</p>



<a name="219068719"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219068719" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Brendan Zabarauskas <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219068719">(Dec 07 2020 at 11:28)</a>:</h4>
<p>I remember that tweet</p>



<a name="219068847"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219068847" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Brendan Zabarauskas <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219068847">(Dec 07 2020 at 11:30)</a>:</h4>
<p>You can probably find videos if you search for Elco Visser if that's more consumable (I often find it a bit easier than launching into papers first, but I'm weird).</p>



<a name="219068926"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219068926" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Brendan Zabarauskas <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219068926">(Dec 07 2020 at 11:30)</a>:</h4>
<p>I think he's the main researcher working on this stuff if you are looking for somebody to chat to: <a href="https://eelcovisser.org/">https://eelcovisser.org/</a></p>



<a name="219069010"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219069010" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Brendan Zabarauskas <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219069010">(Dec 07 2020 at 11:32)</a>:</h4>
<p>/me remembers the days when cyclic imports would crash the rust compiler</p>



<a name="219069385"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219069385" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Brendan Zabarauskas <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219069385">(Dec 07 2020 at 11:36)</a>:</h4>
<p>I wonder if there's anything in the mutually recursive module system stuff (in ML land) that might be of use</p>



<a name="219069429"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219069429" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Brendan Zabarauskas <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219069429">(Dec 07 2020 at 11:37)</a>:</h4>
<p>Might be a bit focused on a specific language feature than a more general theory though</p>



<a name="219069518"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219069518" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219069518">(Dec 07 2020 at 11:38)</a>:</h4>
<p>Heh, I wish we just didn't do this at all. Makes writing fast IDE a pain in the back (as it precludes map-reduce approach: <a href="https://rust-analyzer.github.io/blog/2020/07/20/three-architectures-for-responsive-ide.html#map-reduce">https://rust-analyzer.github.io/blog/2020/07/20/three-architectures-for-responsive-ide.html#map-reduce</a>)</p>



<a name="219069755"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219069755" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Brendan Zabarauskas <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219069755">(Dec 07 2020 at 11:41)</a>:</h4>
<p>yeah, seems rather frustrating <span aria-label="cry" class="emoji emoji-1f622" role="img" title="cry">:cry:</span></p>



<a name="219069870"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219069870" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Brendan Zabarauskas <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219069870">(Dec 07 2020 at 11:43)</a>:</h4>
<p>So yeah, dunno if any of this has helped at all! I do think you might be on the right track with the scope graph stuff - I'm just not sure how close it would be to getting it to getting it to a production implementation</p>



<a name="219069967"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219069967" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219069967">(Dec 07 2020 at 11:44)</a>:</h4>
<p>This all is definitely very helpful!</p>



<a name="219069985"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219069985" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Brendan Zabarauskas <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219069985">(Dec 07 2020 at 11:44)</a>:</h4>
<p>Like, does it support the fixed point stuff you want, and how do you get it to work for a responsive, incremental compiler.</p>



<a name="219069989"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219069989" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219069989">(Dec 07 2020 at 11:44)</a>:</h4>
<p>Even if it turns out to be a negative resul in the end with respect to actual impl D</p>



<a name="219070047"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219070047" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Brendan Zabarauskas <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219070047">(Dec 07 2020 at 11:45)</a>:</h4>
<p>Yeah, still always good to have people looking at this stuff, and sometimes interacting with the researchers, showing them potential use cases/applications that they might not have thought of.</p>



<a name="219070337"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219070337" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219070337">(Dec 07 2020 at 11:49)</a>:</h4>
<p>(the scope graphs parts have dedicated papers and implementations, + talks &amp; videos eg <a href="https://eelcovisser.org/talks/2017/06/20/scope-graphsa-fresh-look-at-name-binding-in-programming-languages/">https://eelcovisser.org/talks/2017/06/20/scope-graphsa-fresh-look-at-name-binding-in-programming-languages/</a>)</p>



<a name="219070452"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219070452" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Brendan Zabarauskas <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219070452">(Dec 07 2020 at 11:50)</a>:</h4>
<p>yeah, papers+implementations are always super nice and handy!</p>



<a name="219070499"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219070499" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219070499">(Dec 07 2020 at 11:51)</a>:</h4>
<p>(fun fact I somehow watched your compose talk yesterday Brendan :)</p>



<a name="219070508"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219070508" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Brendan Zabarauskas <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219070508">(Dec 07 2020 at 11:51)</a>:</h4>
<p>oh no!</p>



<a name="219070521"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219070521" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Brendan Zabarauskas <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219070521">(Dec 07 2020 at 11:52)</a>:</h4>
<p>hahah :)</p>



<a name="219070649"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219070649" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Brendan Zabarauskas <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219070649">(Dec 07 2020 at 11:53)</a>:</h4>
<p>I did finally come up with a name in the year or so since that talk <a href="https://github.com/yeslogic/fathom">https://github.com/yeslogic/fathom</a></p>
<p>(and also figured out a bunch of nasty snags that I glossed over in there, hoping one day I might be able to do a follow up talk on it)</p>



<a name="219070764"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219070764" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219070764">(Dec 07 2020 at 11:55)</a>:</h4>
<p><span class="user-mention silent" data-user-id="201857">Brendan Zabarauskas</span> <a href="#narrow/stream/185405-t-compiler.2Fwg-rls-2.2E0/topic/Formalizing.20name.20resolution/near/219068612">said</a>:</p>
<blockquote>
<p>They have a funny eclipse IDE thing that you can define languages in using these DSLs</p>
</blockquote>
<p>that's "Spoofax" ^^</p>



<a name="219070850"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219070850" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Brendan Zabarauskas <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219070850">(Dec 07 2020 at 11:56)</a>:</h4>
<p>have you played around with Spoofax before?</p>



<a name="219070860"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219070860" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219070860">(Dec 07 2020 at 11:56)</a>:</h4>
<p>(ah you've all already mentioned everything here sorry)</p>



<a name="219070896"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219070896" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219070896">(Dec 07 2020 at 11:57)</a>:</h4>
<p>I haven't but I've read a couple papers, such as the scope graphs and more, and I've seen conference tutorials and talks from Eelco and students</p>



<a name="219070940"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219070940" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219070940">(Dec 07 2020 at 11:57)</a>:</h4>
<p>(including one where he hopes to model Haskell in Spoofax, and SPJ seemed interested :)</p>



<a name="219071006"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219071006" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219071006">(Dec 07 2020 at 11:58)</a>:</h4>
<p><span class="user-mention" data-user-id="201857">@Brendan Zabarauskas</span> have you seen <a href="https://github.com/GaloisInc/daedalus">https://github.com/GaloisInc/daedalus</a>? Seems to be roughly in the same spot as fathom, from the cursory look at it.</p>



<a name="219071031"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219071031" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Brendan Zabarauskas <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219071031">(Dec 07 2020 at 11:58)</a>:</h4>
<p>oooh, not seen that one</p>



<a name="219071062"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219071062" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Brendan Zabarauskas <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219071062">(Dec 07 2020 at 11:59)</a>:</h4>
<p>I'm aware of Kaitai, Nacissus, Everpass/QuackyDucky</p>



<a name="219071131"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219071131" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219071131">(Dec 07 2020 at 12:00)</a>:</h4>
<p>daedalus seems new, I wonder if David Christiansen didn't mention it somewhere</p>



<a name="219071132"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219071132" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Brendan Zabarauskas <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219071132">(Dec 07 2020 at 12:00)</a>:</h4>
<p>and there are some interesting ones for lisp and Dylan</p>



<a name="219071172"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219071172" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Brendan Zabarauskas <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219071172">(Dec 07 2020 at 12:01)</a>:</h4>
<p>yeah this looks pretty close</p>



<a name="219071356"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219071356" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Brendan Zabarauskas <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219071356">(Dec 07 2020 at 12:03)</a>:</h4>
<p>Wonder if the can unparse as well <span aria-label="thinking" class="emoji emoji-1f914" role="img" title="thinking">:thinking:</span></p>



<a name="219071517"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219071517" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Brendan Zabarauskas <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219071517">(Dec 07 2020 at 12:05)</a>:</h4>
<p>OOOH lol the PDF stuff will be interesting for YesLogic</p>



<a name="219072204"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219072204" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219072204">(Dec 07 2020 at 12:14)</a>:</h4>
<p>(if you want to prototype some rust-like rules to validate/invalidate the scope graphs approach, <a href="https://eelcovisser.org/talks/2020/06/16/spoofax-tutorial-at-pldi/">https://eelcovisser.org/talks/2020/06/16/spoofax-tutorial-at-pldi/</a> was the "tutorial" I remember watching as well)</p>



<a name="219207381"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/Formalizing%20name%20resolution/near/219207381" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> okterakt <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/Formalizing.20name.20resolution.html#219207381">(Dec 08 2020 at 13:44)</a>:</h4>
<p>The work on scope graphs is indeed interesting and the nice thing is that it seems somewhat extensible, at a first glance at least. Does anyone know of other relevant papers on the topic? Most of what I've been able to find is related to Eelco Visser's work.</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>